# 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，
# 其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
#  例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
#  返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
#
#  示例 1：
# 输入：numCourses = 2, prerequisites = [[1,0]]
# 输出：[0,1]
# 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
#
#
#  示例 2：
# 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
# 输出：[0,2,1,3]
# 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
# 因此，一个正确的课程顺序是[0,1,2,3] 。另一个正确的排序是[0,2,1,3] 。
#
#  示例 3：
# 输入：numCourses = 1, prerequisites = []
# 输出：[0]
import collections
from typing import List


class Solution:
    def findOrder2(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        """
        拓扑排序(DFS实现)
        对于图中的任意一个节点，它在搜索的过程中有三种状态:
            未搜索(0)：我们还没有搜索到这个节点；
            搜索中(1)：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；
            已完成(2)：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

        每一轮的搜索搜索开始时，任取一个 未搜索 的节点 node开始进行 DFS。
            将当前搜索的节点 node 标记为「搜索中」，遍历该节点的每一个相邻节点 neighbor：
                如果 neighbor 为 0，那么开始搜索 neighbor，待搜索所有邻接点完成后 回溯到 node；
                如果 neighbor 为 1，那么说明找到了图中的一个环，因此是不存在拓扑排序的；
                如果 neighbor 为 2，那么说明 neighbor 已经在栈中了，而 node 还不在栈中，因此 node 无论何时入栈都不会影响到 (node,neighbor) 之前的拓扑关系。
            当 node 的所有相邻节点都为「已完成」时，将 node 放入栈中，并将其标记为「已完成」
        :param numCourses:
        :param prerequisites:
        :return:
        """
        res = []
        adjList = collections.defaultdict(list)
        for a, b in prerequisites:  # 初始化邻接表
            adjList[b].append(a)
        existRing = False  # 图中是否存在环的标志
        visited = [0] * numCourses  # 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成

        def dfs(node: int) -> None:
            nonlocal existRing
            visited[node] = 1
            for neighbor in adjList[node]:  # DFS遍历当前节点的所有邻接点
                if not visited[neighbor]:
                    dfs(neighbor)
                elif visited[neighbor] == 1:
                    existRing = True
                    return
            visited[node] = 2
            res.append(node)

        for i in range(numCourses):  # 对所有节点进行dfs
            if not existRing and visited[i] == 0:
                dfs(i)
            elif existRing:  # 只要检测到有环就肯定不能完成拓扑排序，也不需要再进行下去了
                return []
        return res[::-1]

    def findOrder1(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        """
        拓扑排序(BFS实现)
        先找到入度为0的节点，以其为起点"一层一层的删除入度为0的节点"，并更新节点的入度值
        :param numCourses:
        :param prerequisites:
        :return:
        """
        res = []
        adjList = collections.defaultdict(list)
        inDegresses = [0] * numCourses  # 记录每个顶点的入度
        for a, b in prerequisites:  # 初始化邻接表统计每个顶点的入度
            adjList[b].append(a)
            inDegresses[a] += 1

        q = collections.deque()
        for i in range(numCourses):  # 找到所有入度为0的节点，开始遍历
            if not inDegresses[i]:
                q.append(i)
        while q:
            tmpNode = q.popleft()
            if not inDegresses[tmpNode]:  # 某个节点的入度为0代表不需要前置，可以"删除"
                res.append(tmpNode)
            for neighbor in adjList[tmpNode]:
                inDegresses[neighbor] -= 1  # 邻接点的入度减一，相当于将 tmpNode 节点"删除"
                if not inDegresses[neighbor]:  # 邻接点的入度等于0时将邻接点入队
                    q.append(neighbor)
        return res if len(res) == numCourses else []

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        return self.findOrder2(numCourses, prerequisites)


if __name__ == "__main__":
    numCourses, prerequisites = 4, [[1, 0], [2, 0], [3, 1], [3, 2]]
    numCourses, prerequisites = 2, [[0, 1], [1, 0]]
    print(Solution().findOrder(numCourses, prerequisites))
